#include "gtest/gtest.h"

#include "util.h"

#include <list>
#include <algorithm>
#include <initializer_list>


struct Node {
    int val;
    Node * next;
    Node(int val) :val(val), next(NULL){}
    Node(int val, Node * next) : val(val), next(next) {}
};

class  List {
public:
    List(std::initializer_list<int> ints)
    : head(new Node(0, NULL))
    , tail(head)
    , size(0){
        std::initializer_list<int>::iterator it = ints.begin();
        for(; it != ints.end(); ++it){
            push_back(*it);
        }
    }
    List()
    : head(new Node(0, NULL))
    , tail(head)
    , size(0) 
    {
    }
    ~List(){
        clear();
        delete head;
        tail = head = NULL;
    }
    void push_back(int i){
        Node * node = new Node(i);
        tail->next = node;
        tail = node;
        ++size;
    }
    void clear(){
        Node * node = head->next;
        while(node != NULL){ 
            head->next = node->next;
            delete node;
            node = head->next;
        };
        size = 0;
        tail = head;
    }
    void reverse(List & out){
        Node * node = head->next;
        while(node != NULL){
            head->next = node->next; //remove node from this->head

            node->next = out.head->next; // add the node to out chain; node---> out.first.node
            out.head->next = node;      // step 2;  out.head->next =====> node
            ++(out.size);

            node = head->next;      // node to this.head.next
            --size;
        }
    }
    void print(const std::string & msg) const{
        std::cout << msg << " : ";
        Node * node = head->next;
        while(node != NULL){
            std::cout << node->val << ", ";
            node = node->next;
        }
        std::cout << std::endl;
    }
    bool equal(const List  & right) const{
        if(&right == this) return true;
        if(size != right.size) return false;

        Node * rNode = right.head->next;
        Node * node = head->next;
        while(node != NULL && rNode != NULL){
            if(node->val != rNode->val) return false;    
            node = node->next;
            rNode = rNode->next;
        }
        if(node != NULL) return false;
        if(rNode != NULL) return false;
        return true;
    }
    int getSize()const {
        return size;
    }

    void _swap(Node * pre){
        assert(pre != NULL);
        if(pre->next == NULL) return; // zero node of this round
        Node * first = pre->next; // first != NULL

        if(first->next == NULL) return ; // single node of this round
        Node * second = first->next;// second != NULL
    
        pre->next = second; 
        first->next = second->next;
        second->next = first;
        
        _swap(first);
    }
    void swapFirstTwo(){
        _swap(head);
    }

public:
    Node * head;
    Node * tail;
    int size;
};





class ListTest : public testing::Test {
    void SetUp(){
        N = 5;
        for(int i =0; i < N ; ++i){
            expectOrdered.push_back(i);
            expectReversed.push_back(N - i - 1);
        }
    }

protected:
    int N;
    List expectOrdered;
    List expectReversed;
};


TEST_F(ListTest, testInit){
    ASSERT_EQ(N, expectOrdered.getSize());
    expectOrdered.print("expectOrdered");
    ASSERT_EQ(N, expectOrdered.getSize());

    ASSERT_EQ(N, expectReversed.getSize());
    expectReversed.print("expectReversed");
    ASSERT_EQ(N, expectReversed.getSize());
}
TEST_F(ListTest, testEqual){
    List in = {0, 1, 2, 3, 4, };
    ASSERT_EQ(N, in.getSize());

    ASSERT_TRUE(in.equal(expectOrdered)); //all for it

    in.clear();
    ASSERT_EQ(0, in.getSize());
}

TEST_F(ListTest, testReverse){
    List in = {0, 1, 2, 3, 4, };

    List out;
    in.reverse(out);
    ASSERT_EQ(0, in.getSize());
    ASSERT_EQ(N, out.getSize());
    ASSERT_TRUE(out.equal(expectReversed));
}


TEST_F(ListTest, testSwapTwo){
    {
        List expect = {};
        List in = {};
        in.swapFirstTwo();
        ASSERT_TRUE(expect.equal(in));
    }
    {
        List expect = {0, };
        List in = {0,};
        in.swapFirstTwo();
        ASSERT_TRUE(expect.equal(in));
    }
    {
        List expect = {1, 0};
        List in = {0, 1};
        in.swapFirstTwo();
        ASSERT_TRUE(expect.equal(in));
    }
    {
        List expect = {1, 0, 2};
        List in = {0, 1, 2 };
        in.swapFirstTwo();
        ASSERT_TRUE(expect.equal(in));
    }
    {
        List expect = {1, 0, 3, 2};
        List in = {0, 1, 2, 3};
        in.swapFirstTwo();
        ASSERT_TRUE(expect.equal(in));
    }
    {
        List expect = {1, 0, 3, 2, 4};
        List in = {0, 1, 2, 3, 4};
        in.swapFirstTwo();
        ASSERT_TRUE(expect.equal(in));
    }
}
